package com.lh.nk;

/**
 * @author: linghao
 * @since: 2023/1/23
 *
 * 描述
 * 给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
 *
 * 动态规划
 */
public class 编辑距离二NC35 {

    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     *
     * 分析：
     *  str1为空，str2不为空时，  ic操作变为一致的
     *  str1不为空，str2为空，str1 位置 i 字符 变成 str2 空字符 删除操作
     *
     *  str1和str2都不为空时，
     *   当两个元素相等时，不进行操作 dp[i][j]=dp[i-1][j-1]
     *   不相等时，dp[i][j] = Math.min(insert, delete, replace)
     * int insert = dp[i][j-1] + 1; i个编辑成j-1个字符，再插入一个j
     * int delete = dp[i-1][j] + 1; i-1个编辑成j个字母，再删除一个i
     * int replace = dp[i-1][j-1] + 1; i-1个编辑成j-1个字母，再将i替换成j
     */
    public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
        // write code here
        int m = str1.length();
        int n = str2.length();
        int[][] dp = new int[m+1][n+1];
        //当str2为空串时,删除操作
        for(int i=1;i<=m;i++){
            dp[i][0] = dp[i-1][0]+dc;
        }
        //当str1为空串时,新增操作
        for(int i=1;i<=n;i++){
            dp[0][i] = dp[0][i-1]+ic;
        }

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(str1.charAt(i-1) == str2.charAt(j-1)){  //不需要任何操作
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.min(dp[i][j-1]+ic,Math.min(dp[i-1][j-1]+rc,dp[i-1][j]+dc));
                }
            }
        }
        return dp[m][n];
    }
}
